package com.lsa.edmonds.chap8;

import java.util.List;

import com.lsa.helpers.CollectionUtils;
import com.lsa.helpers.IntArrayListAdapter;
import com.lsa.helpers.SubListAdapter;
import com.lsa.helpers.Utils;
import com.lsa.shenn.common.InsertionSort;
import com.lsa.shenn.common.Sorter;

public class QuickSort implements Sorter
{
    private static int SIMPLE_SORT_SIZE = 3;
    private Sorter sorter = new InsertionSort();
    
    public int[] sort(int[] array)
    {
        sort(IntArrayListAdapter.adapt(array));
        return array;
    }

    public List<Integer> sort(List<Integer> array)
    {   
        sort(array, 0, array.size() - 1);
        return array;
    }
    
    void sort(List<Integer> array, int from, int to)
    {
        if (to - from + 1 < 2)
        {
            return;
        }
        
        if (to - from + 1 < SIMPLE_SORT_SIZE)
        {
            sorter.sort(SubListAdapter.adapt(array, from, to));
            return;
        }
        
        //int pivotIdx = Utils.random(from + 1, to - 1);
        int pivotIdx = from + (to - from) / 2;
        pivotIdx = CollectionUtils.pivotDivide(array, from, to, pivotIdx);
        
        sort(array, from, pivotIdx - 1);
        sort(array, pivotIdx + 1, to);
    }
}
